<html>
<head>
  <meta HTTP-EQUIV="Content-Type" CONTENT="text/html;charset=ISO-8859-1">
  <title>ekozinec.m</title>
<link rel="stylesheet" type="text/css" href="../../../m-syntax.css">
</head>
<body>
<code>
<span class=defun_kw>function</span>&nbsp;<span class=defun_out>model</span>=<span class=defun_name>ekozinec</span>(<span class=defun_in>data,options,init_model</span>)<br>
<span class=h1>%&nbsp;EKOZINEC&nbsp;Kozinec's&nbsp;algorithm&nbsp;for&nbsp;eps-optimal&nbsp;separating&nbsp;hyperplane.</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;<span class=help_field>Synopsis:</span></span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;=&nbsp;ekozinec(data)</span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;=&nbsp;ekozinec(data,options)</span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;=&nbsp;ekozinec(data,options,init_model)</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;<span class=help_field>Description:</span></span><br>
<span class=help>%&nbsp;&nbsp;This&nbsp;function&nbsp;is&nbsp;implementation&nbsp;of&nbsp;the&nbsp;Kozinec's&nbsp;algorithm</span><br>
<span class=help>%&nbsp;&nbsp;with&nbsp;eps-optimality&nbsp;stopping&nbsp;condition&nbsp;[SH10].&nbsp;The&nbsp;algorithm&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;finds&nbsp;the&nbsp;eps-optimal&nbsp;separating&nbsp;hyperplane.</span><br>
<span class=help>%&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;model=ekozinec(data)&nbsp;the&nbsp;Kozinec's&nbsp;rule&nbsp;is&nbsp;used&nbsp;to&nbsp;find&nbsp;the&nbsp;closest&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;points&nbsp;w1,&nbsp;w2&nbsp;from&nbsp;the&nbsp;convex&nbsp;hulls&nbsp;of&nbsp;the&nbsp;vectors&nbsp;from&nbsp;the&nbsp;first&nbsp;and&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;the&nbsp;second&nbsp;class.&nbsp;The&nbsp;found&nbsp;points&nbsp;determine&nbsp;the&nbsp;optimal&nbsp;separating&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;hyperplane.&nbsp;</span><br>
<span class=help>%&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;model=ekozinec(data,options)&nbsp;specifies&nbsp;stopping&nbsp;conditions&nbsp;of</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;the&nbsp;algorithm&nbsp;in&nbsp;structure&nbsp;options:</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;.eps&nbsp;[1x1]&nbsp;...&nbsp;controls&nbsp;how&nbsp;close&nbsp;is&nbsp;the&nbsp;found&nbsp;solution&nbsp;to</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;the&nbsp;optimal&nbsp;hyperplane&nbsp;in&nbsp;terms&nbsp;of&nbsp;margin&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(default&nbsp;eps=0.01).&nbsp;The&nbsp;options&nbsp;for&nbsp;eps&nbsp;are:&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eps&nbsp;&gt;&nbsp;0&nbsp;...&nbsp;eps-optimal&nbsp;hyperplane&nbsp;is&nbsp;sought&nbsp;for.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eps&nbsp;==&nbsp;0&nbsp;...&nbsp;algorithm&nbsp;converges&nbsp;to&nbsp;the&nbsp;optimal&nbsp;hyperplane&nbsp;(but&nbsp;it</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;does&nbsp;not&nbsp;have&nbsp;to&nbsp;stop&nbsp;in&nbsp;finite&nbsp;number&nbsp;of&nbsp;iterations).</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eps&nbsp;&lt;&nbsp;0&nbsp;...&nbsp;algorithm&nbsp;stops&nbsp;when&nbsp;the&nbsp;separating&nbsp;hyperplane&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;is&nbsp;found&nbsp;(zero&nbsp;training&nbsp;error)&nbsp;regardless&nbsp;the&nbsp;margin&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;so&nbsp;it&nbsp;solves&nbsp;the&nbsp;same&nbsp;task&nbsp;as&nbsp;the&nbsp;ordinary&nbsp;Perceptron.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;.tmax&nbsp;[1x1]...&nbsp;maximal&nbsp;number&nbsp;of&nbsp;iterations.</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;=&nbsp;ekozinec(data,options,init_model)&nbsp;specifies&nbsp;initial&nbsp;model</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;which&nbsp;must&nbsp;contain:</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;.W1&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;...&nbsp;Vector&nbsp;from&nbsp;the&nbsp;first&nbsp;convex&nbsp;hull.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;.W2&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;...&nbsp;Vector&nbsp;from&nbsp;the&nbsp;second&nbsp;convex&nbsp;hull.</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;<span class=help_field>Input:</span></span><br>
<span class=help>%&nbsp;&nbsp;data&nbsp;[struct]&nbsp;Labeled&nbsp;(binary)&nbsp;training&nbsp;data.&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.X&nbsp;[dim&nbsp;x&nbsp;num_data]&nbsp;Input&nbsp;vectors.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.y&nbsp;[1&nbsp;x&nbsp;num_data]&nbsp;Labels&nbsp;(1&nbsp;or&nbsp;2).</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;&nbsp;options&nbsp;[struct]&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.eps&nbsp;[real]&nbsp;Controls&nbsp;how&nbsp;closeness&nbsp;to&nbsp;the&nbsp;optimal&nbsp;hypeprlane&nbsp;(see&nbsp;above).</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.tmax&nbsp;[1x1]&nbsp;Maximal&nbsp;number&nbsp;of&nbsp;iterations&nbsp;(default&nbsp;tmax=inf).</span><br>
<span class=help>%&nbsp;&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;init_model&nbsp;[struct]&nbsp;Initial&nbsp;model;&nbsp;must&nbsp;contain&nbsp;items</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;.W1&nbsp;[dim&nbsp;x&nbsp;1],&nbsp;.W2&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;see&nbsp;above.</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;<span class=help_field>Output:</span></span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;[struct]&nbsp;Binary&nbsp;linear&nbsp;classifier:</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.W&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;Normal&nbsp;vector&nbsp;of&nbsp;hyperplane.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.b&nbsp;[1x1]&nbsp;Bias&nbsp;of&nbsp;hyperplane.</span><br>
<span class=help>%&nbsp;&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.W1&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;The&nbsp;nearest&nbsp;vector&nbsp;of&nbsp;the&nbsp;first&nbsp;convex&nbsp;hull.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.W2&nbsp;[dim&nbsp;x&nbsp;1]&nbsp;The&nbsp;nearest&nbsp;vector&nbsp;of&nbsp;the&nbsp;second&nbsp;convex&nbsp;hull.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.margin&nbsp;[1x1]&nbsp;Margin&nbsp;of&nbsp;the&nbsp;found&nbsp;hyperplane.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.exitflag&nbsp;[1x1]&nbsp;1&nbsp;...&nbsp;eps-optimality&nbsp;condition&nbsp;satisfied&nbsp;or&nbsp;separating</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hyperplane&nbsp;has&nbsp;been&nbsp;found&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;...&nbsp;number&nbsp;of&nbsp;iterations&nbsp;exceeded&nbsp;tmax.</span><br>
<span class=help>%&nbsp;&nbsp;&nbsp;.t&nbsp;[1x1]&nbsp;Number&nbsp;of&nbsp;iterations.</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;<span class=help_field>Example:</span></span><br>
<span class=help>%&nbsp;&nbsp;data&nbsp;=&nbsp;genlsdata(&nbsp;2,&nbsp;50,&nbsp;1);</span><br>
<span class=help>%&nbsp;&nbsp;model&nbsp;=&nbsp;ekozinec(data,&nbsp;struct('eps',0.01));</span><br>
<span class=help>%&nbsp;&nbsp;figure;&nbsp;ppatterns(data);&nbsp;pline(model);&nbsp;</span><br>
<span class=help>%</span><br>
<span class=help>%&nbsp;See&nbsp;also&nbsp;</span><br>
<span class=help>%&nbsp;&nbsp;PERCEPTRON,&nbsp;MPERCEPTRON,&nbsp;LINCLASS.</span><br>
<span class=help>%</span><br>
<hr>
<span class=help1>%&nbsp;<span class=help1_field>About:</span>&nbsp;Statistical&nbsp;Pattern&nbsp;Recognition&nbsp;Toolbox</span><br>
<span class=help1>%&nbsp;(C)&nbsp;1999-2003,&nbsp;Written&nbsp;by&nbsp;Vojtech&nbsp;Franc&nbsp;and&nbsp;Vaclav&nbsp;Hlavac</span><br>
<span class=help1>%&nbsp;&lt;a&nbsp;href="http://www.cvut.cz"&gt;Czech&nbsp;Technical&nbsp;University&nbsp;Prague&lt;/a&gt;</span><br>
<span class=help1>%&nbsp;&lt;a&nbsp;href="http://www.feld.cvut.cz"&gt;Faculty&nbsp;of&nbsp;Electrical&nbsp;Engineering&lt;/a&gt;</span><br>
<span class=help1>%&nbsp;&lt;a&nbsp;href="http://cmp.felk.cvut.cz"&gt;Center&nbsp;for&nbsp;Machine&nbsp;Perception&lt;/a&gt;</span><br>
<br>
<span class=help1>%&nbsp;<span class=help1_field>Modifications:</span></span><br>
<span class=help1>%&nbsp;19-may-2004,&nbsp;VF</span><br>
<span class=help1>%&nbsp;3-may-2004,&nbsp;VF</span><br>
<span class=help1>%&nbsp;17-Sep-2003,&nbsp;VF</span><br>
<span class=help1>%&nbsp;17-Feb-2003,&nbsp;VF</span><br>
<span class=help1>%&nbsp;16-Feb-2003,&nbsp;VF</span><br>
<span class=help1>%&nbsp;21-apr-2001,&nbsp;V.Franc,&nbsp;created</span><br>
<br>
<hr>
<span class=comment>%&nbsp;get&nbsp;data&nbsp;dimensions</span><br>
[dim,num_data]&nbsp;=&nbsp;size(data.X);<br>
inx1=find(data.y==1);<br>
inx2=find(data.y==2);<br>
<br>
<span class=comment>%&nbsp;Process&nbsp;input&nbsp;arguments</span><br>
<span class=comment>%&nbsp;--------------------------</span><br>
<span class=keyword>if</span>&nbsp;<span class=stack>nargin</span>&nbsp;&lt;&nbsp;2,&nbsp;&nbsp;options&nbsp;=&nbsp;[];&nbsp;<span class=keyword>else</span>&nbsp;options&nbsp;=&nbsp;c2s(options);&nbsp;<span class=keyword>end</span><br>
<span class=keyword>if</span>&nbsp;~isfield(options,<span class=quotes>'tmax'</span>),&nbsp;options.tmax&nbsp;=&nbsp;inf;&nbsp;<span class=keyword>end</span><br>
<span class=keyword>if</span>&nbsp;~isfield(options,<span class=quotes>'eps'</span>),&nbsp;options.eps&nbsp;=&nbsp;0.01;&nbsp;<span class=keyword>end</span><br>
<span class=keyword>if</span>&nbsp;~isfield(options,<span class=quotes>'verb'</span>),&nbsp;options.verb&nbsp;=&nbsp;0;&nbsp;<span class=keyword>end</span><br>
<br>
<span class=keyword>if</span>&nbsp;<span class=stack>nargin</span>&nbsp;&lt;&nbsp;3,<br>
&nbsp;&nbsp;<span class=comment>%&nbsp;creates&nbsp;init&nbsp;model</span><br>
&nbsp;&nbsp;<span class=comment>%&nbsp;--------------------------</span><br>
&nbsp;&nbsp;inx1=find(data.y==1);&nbsp;&nbsp;&nbsp;inx2=find(data.y==2);<br>
&nbsp;&nbsp;model.W1&nbsp;=&nbsp;data.X(:,inx1(1));<br>
&nbsp;&nbsp;model.W2&nbsp;=&nbsp;data.X(:,inx2(1));<br>
<span class=keyword>else</span><br>
&nbsp;&nbsp;<span class=comment>%&nbsp;take&nbsp;init&nbsp;model&nbsp;from&nbsp;input</span><br>
&nbsp;&nbsp;<span class=comment>%--------------------------------</span><br>
&nbsp;&nbsp;model&nbsp;=&nbsp;init_model;<br>
<span class=keyword>end</span><br>
<br>
model.t&nbsp;=&nbsp;0;&nbsp;<br>
model.exitflag&nbsp;=&nbsp;0;<br>
<br>
<span class=comment>%&nbsp;main&nbsp;loop</span><br>
<span class=comment>%-----------------------------</span><br>
<span class=keyword>while</span>&nbsp;model.exitflag&nbsp;==&nbsp;0&nbsp;&&nbsp;options.tmax&nbsp;&gt;&nbsp;model.t,<br>
&nbsp;&nbsp;&nbsp;<br>
&nbsp;&nbsp;model.t&nbsp;=&nbsp;model.t&nbsp;+&nbsp;1;<br>
<br>
&nbsp;&nbsp;dW&nbsp;=&nbsp;(model.W1&nbsp;-&nbsp;model.W2);<br>
&nbsp;&nbsp;norm_dW&nbsp;=&nbsp;norm(&nbsp;dW&nbsp;);<br>
&nbsp;&nbsp;<br>
&nbsp;&nbsp;projx&nbsp;=&nbsp;data.X'*dW;<br>
&nbsp;&nbsp;<br>
&nbsp;&nbsp;projx(inx1)&nbsp;=&nbsp;(projx(inx1)&nbsp;-&nbsp;model.W2'*dW)/norm_dW;<br>
&nbsp;&nbsp;projx(inx2)&nbsp;=&nbsp;(-projx(inx2)&nbsp;+&nbsp;model.W1'*dW)/norm_dW;<br>
&nbsp;&nbsp;<br>
&nbsp;&nbsp;[min_proj,&nbsp;min_inx]&nbsp;=&nbsp;min(projx);<br>
<br>
&nbsp;&nbsp;<span class=comment>%&nbsp;bound&nbsp;for&nbsp;separating&nbsp;or&nbsp;eps-optimal&nbsp;separating&nbsp;hyperplane&nbsp;</span><br>
&nbsp;&nbsp;<span class=keyword>if</span>&nbsp;options.eps&nbsp;&lt;&nbsp;0,&nbsp;bound&nbsp;=&nbsp;norm_dW/2;&nbsp;<span class=keyword>else</span>&nbsp;bound=norm_dW-options.eps/2;&nbsp;<span class=keyword>end</span><br>
&nbsp;&nbsp;<br>
&nbsp;&nbsp;<span class=keyword>if</span>&nbsp;min_proj&nbsp;&lt;=&nbsp;bound,<br>
&nbsp;&nbsp;&nbsp;&nbsp;xt=data.X(:,min_inx);<br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;<span class=comment>%&nbsp;Updata&nbsp;-&nbsp;Kozinec's&nbsp;rule</span><br>
&nbsp;&nbsp;&nbsp;&nbsp;<span class=keyword>if</span>&nbsp;data.y(min_inx)&nbsp;==&nbsp;1,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;W1x&nbsp;=&nbsp;model.W1-xt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp;min(1,&nbsp;dW<span class=quotes>'*W1x/&nbsp;(W1x'</span>*W1x));&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;model.W1&nbsp;=&nbsp;model.W1&nbsp;*&nbsp;(1&nbsp;-&nbsp;k)&nbsp;+&nbsp;xt&nbsp;*&nbsp;k;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<span class=keyword>else</span><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;W2x&nbsp;=&nbsp;model.W2-xt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp;min(1,&nbsp;-dW<span class=quotes>'*W2x&nbsp;/&nbsp;(W2x'</span>*W2x));<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;model.W2&nbsp;=&nbsp;model.W2&nbsp;*&nbsp;(1&nbsp;-&nbsp;k)&nbsp;+&nbsp;xt&nbsp;*&nbsp;k;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<span class=keyword>end</span><br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;model.exitflag&nbsp;=&nbsp;0;<br>
&nbsp;&nbsp;<span class=keyword>else</span><br>
&nbsp;&nbsp;&nbsp;&nbsp;model.exitflag&nbsp;=&nbsp;1;<br>
&nbsp;&nbsp;<span class=keyword>end</span><br>
<br>
&nbsp;&nbsp;<span class=comment>%&nbsp;print&nbsp;info</span><br>
&nbsp;&nbsp;<span class=keyword>if</span>&nbsp;options.verb&nbsp;==&nbsp;1&nbsp;&&nbsp;mod(model.t,100)&nbsp;==&nbsp;0,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class=io>fprintf</span>(<span class=quotes>'iter&nbsp;%d:&nbsp;upper_bound&nbsp;=&nbsp;%f,&nbsp;lower_bound&nbsp;=&nbsp;%f,&nbsp;dif&nbsp;=&nbsp;%f\n'</span>,&nbsp;...<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;model.t,&nbsp;norm_dW/2,&nbsp;min_proj/2,&nbsp;(norm_dW-min_proj)/2&nbsp;);&nbsp;&nbsp;<br>
&nbsp;&nbsp;<span class=keyword>end</span><br>
&nbsp;&nbsp;<br>
<span class=keyword>end</span><br>
<br>
model.b&nbsp;=&nbsp;0.5&nbsp;*&nbsp;(model.W2<span class=quotes>'*model.W2&nbsp;-&nbsp;model.W1'</span>*model.W1);<br>
model.W&nbsp;=&nbsp;model.W1&nbsp;-&nbsp;model.W2;<br>
model.margin&nbsp;=&nbsp;min_proj/2;<br>
model.fun&nbsp;=&nbsp;<span class=quotes>'linclass'</span>;<br>
<br>
<span class=jump>return</span>;<br>
<br>
</code>
